/*
 * @Author: gitee_com_zb
 * @Date: 2024-11-28 17:27:19
 * @LastEditors: gitee_com_zb
 * @LastEditTime: 2024-11-28 17:27:26
 * @FilePath: /algorithm/每日一题2.合并两个有序数组(easy).cpp
 * @Description: 题目链接 https://leetcode.cn/problems/merge-sorted-array
 */

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        // 1. 直接合并后排序(耍赖皮)
        // for(int i = 0; i < n; i++) nums1[m + i] = nums2[i];
        // sort(nums1.begin(), nums1.end());
        
        // 2. 双指针优化,取出较大值,向nums1从后向前插入
        int p1 = m - 1, p2 = n - 1, pos = m + n - 1;
        while(p1 >= 0 && p2 >= 0) {
            if(nums1[p1] > nums2[p2]) nums1[pos--] = nums1[p1--];
            else nums1[pos--] = nums2[p2--];
        }
        while(p1 >= 0) nums1[pos--] = nums1[p1--];
        while(p2 >= 0) nums1[pos--] = nums2[p2--];
    }
};
